import { Compare, defaultCompare, ICompareFunction } from '../../util';

/**
 * 希尔排序要用到的直接插入
 * @param array 目标数组
 * @param increment 增量
 * @param compareFn 比较函数
 */
function insertionSort<T>(array: T[], increment: number, compareFn: ICompareFunction<T>) {
    /*
        直接排序是从索引1开始的，因为他们没有间隔，而这里是有间隔increment，所以要从increment开始。
        直接排序首先是索引1这项与索引0这项比较插入，然后索引2与索引1索引0比较插入，索引3与索引2索引1索引0比较插入...
        按理说，这里应该索引increment这项与索引0比较插入，然后索引2*increment与索引increment索引0比较插入...也就是说
        i应该是i += increment，但这里实际上是i ++，为什么呢？是因为要尽可能让数组里所有距离increment进行插入排序，你
        不能只让0开始并距离increment的进行插入排序，那就得外套一层increment循环来尽可能让数组里所有距离increment进行
        插入排序，但这样的处理还不如i ++来得更有效率。
    */
    for (let i = increment; i < array.length; i ++) {
        // 当前项temp，即将插入已排序列表中
        const temp: T = array[i];
        // 当前项的前一项，是已排序列表的最左侧项并且是最大的一项
        let j = i - increment;
        // temp比已排序列表的最大项还大或相等，temp不用插入了直接下一轮
        if (compareFn(temp, array[j]) !== Compare.LESS_THAN) {
            continue;
        }
        // 从有序列表的左边往右遍历，temp更小可以插入，那么array[j]需要左挪腾出位置
        while (j >= 0 && compareFn(temp, array[j]) === Compare.LESS_THAN) {
            // array[j]往左挪，挪到j + increment
            array[j + increment] = array[j];
            // 从有序列表的左边往右遍历，j要自减increment
            j -= increment;
        }
        // 最后空出的位置，将temp插到空位
        array[j + increment] = temp;
    }
}
/**
 * 希尔算法D.Shell最初的算法，1959年发表
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量increment，是在数组长度上取一半再向下取整，之后一直取一半再向下取整，直到增量为1
 */
export function shellsortSh<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，初始化时是最大值，取length的一半并向下取整
    let increment = Math.floor(length / 2);
    // 增量increment最小只能为1
    while (increment >= 1) {
        // 插入排序
        insertionSort(array, increment, compareFn);
        // 每轮结束，让之前增量一半并向下取整
        increment = Math.floor(increment / 2);
    }
    return array;
}
/**
 * 希尔算法，Lazarus-Frank改良，1960年发表
 * @param array 原数组
 * @param compareFn 比较函数
 * 在D.Shell基础上，如果增量算出是偶数，那就减1
 */
export function shellsortLF<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，初始化时是最大值，取length的一半并向下取整
    let increment = Math.floor(length / 2);
    // 增量increment最小只能为1
    while (increment >= 1) {
        // 增量如果是偶数，就减1
        if ((increment % 2) === 0) {
            increment --;
        }
        // 插入排序
        insertionSort(array, increment, compareFn);
        // 每轮结束，让之前增量一半并向下取整
        increment = Math.floor(increment / 2);
    }
    return array;
}
/**
 * 希尔算法，Hibbard改良，1963年发表
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：1, 3, 7, 15, 31, 63 ... 2^i-1
 * 相邻两项的关系：k=k*2+1
 */
export function shellsortHb<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取1，然后用迭代算出它的最大值
    let increment = 1;
    // 利用k=k*2+1的关系，求出increment的最大值。
    // 不必纠结(length-1)/2还是length/2，length足够大时差异很小
    while (increment < Math.floor((length - 1) / 2)) {
        increment = increment * 2 + 1;
    }
    // 增量increment最小只能为1
    while (increment >= 1) {
        // 插入排序
        insertionSort(array, increment, compareFn);
        // 每轮结束，利用k=k*2+1的关系，求出下一个increment
        increment = Math.floor((increment - 1) / 2);
    }
    return array;
}
/**
 * 希尔算法，Papernov-Stasevich改良，1965年发表
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：1, 3, 5, 9, 17, 33, 65 ...
 * 除了第一项，其他相邻两项的关系：k=k*2-1
 */
export function shellsortPS<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取2，然后用迭代算出它的最大值
    let increment = 2;
    // 利用k=k*2-1的关系，求出increment的最大值
    while (increment < Math.floor((length + 1) / 2)) {
        increment = increment * 2 - 1;
    }
    // 这里比较特殊，增量increment最小只能为2，并且这个2不是直接用，要转成1
    while (increment >= 2) {
        increment = increment === 2 ? 1 : increment;
        // 插入排序
        insertionSort(array, increment, compareFn);
        // 每轮结束，利用k=k*2-1的关系，求出下一个increment
        increment = Math.floor((increment + 1) / 2);
    }
    return array;
}
/**
 * 希尔算法，Knuth改良
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：1, 4, 13, 40, 121, 364 ... (3^i-1)/2
 * 相邻两项的关系：k=k*3+1
 * 建议在n<1000也就是元素个数少于1000时使用
 */
export function shellsortKn<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取1，然后用迭代算出它的最大值
    let increment = 1;
    // 利用k=k*3+1的关系，求出increment的最大值
    while (increment < Math.floor((length - 1) / 3)) {
        increment = increment * 3 + 1;
    }
    // 增量increment最小只能为1
    while (increment >= 1) {
        // 插入排序
        insertionSort(array, increment, compareFn);
        // 每轮结束，利用k=k*3+1的关系，求出下一个increment
        increment = Math.floor((increment - 1) / 3);
    }
    return array;
}
/**
 * 希尔算法，Pratt改良，1971年发表
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：1, 7, 8, 49, 56, 64, 343, 392, 448, 512, 2401, ...
 * 通项公式：7^p*8^q （其中p、q为非负整数）
 */
export function shellsortPr<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取1，然后用迭代算出它的最大值
    let increment = 1;
    // 增量数组，相连项没有没有明显的关系所以只能存临时数组里了
    const incrementArr: number[] = [];
    resultIn: for (let index = 0; true; index ++) {
        // 通项公式：7^p*8^q，求出increment的最大值
        for (let i = index; i >= 0; i --) {
            // p + q是等于index的
            increment = Math.pow(7, i) * Math.pow(8, index - i);
            // increment不能超过length
            if (increment < length) {
                incrementArr.push(increment);
            } else {
                break resultIn;
            }
        }
    }
    // 遍历增量数组
    for (let i = incrementArr.length - 1; i >= 0; i --) {
        // 从最大的开始
        increment = incrementArr[i];
        // 插入排序
        insertionSort(array, increment, compareFn);
    }
    return array;
}
/**
 * 希尔算法，Sedgewick改良，1982年发表。优于Hibbard和Knuth
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：1, 8, 23, 77, 281, 1073, 4193, 16577...
 * 除了第一项的通项公式：4*2^(2*i)+3*2^i+1（其中i为0,1,2,3,4...）
 */
export function shellsortSe82<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取1，然后用迭代算出它的最大值
    let increment = 1;
    // 增量数组，相连项没有没有明显的关系所以只能存临时数组里了
    const incrementArr: number[] = [1];
    for (let index = 0; true; index ++) {
        // 通项公式：4*2^(2*i)+3*2^i+1，求出increment的最大值
        increment = 4 * Math.pow(2, 2 * index) + 3 * Math.pow(2, index) + 1;
        // increment不能超过length
        if (increment < length) {
            incrementArr.push(increment);
        } else {
            break;
        }
    }
    // 遍历增量数组
    for (let i = incrementArr.length - 1; i >= 0; i --) {
        // 从最大的开始
        increment = incrementArr[i];
        // 插入排序
        insertionSort(array, increment, compareFn);
    }
    return array;
}
/**
 * 希尔算法，Incerpj-Sedgewick改良，1985年发表
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：
 * 1                            此时index=1
 * 3, // a1                     此时index=2，缺的是a2
 * 7, // a2                     此时index=2，缺的是a1
 * 21, // a1*a2                 此时index=3，缺的是a3
 * 48, // a1*a3                 此时index=3，缺的是a2
 * 112, // a2*a3                此时index=3，缺的是a1
 * 336, // a1*a2*a3             此时index=4，缺的是a4
 * 861, // a1*a2*a4             此时index=4，缺的是a3
 * 1968, // a1*a3*a4            此时index=4，缺的是a2
 * 4592, // a2*a3*a4            此时index=4，缺的是a1
 * 13776, // a1*a2*a3*a4        此时index=5，缺的是a5
 * 33936, // a1*a2*a3*a5        此时index=5，缺的是a4
 * 86961, // a1*a2*a4*a5        此时index=5，缺的是a3
 * 198768, // a1*a3*a4*a5       此时index=5，缺的是a2
 * 463792, // a2*a3*a4*a5       此时index=5，缺的是a1
 * 1391376, // a1*a2*a3*a4*a5   此时index=6，缺的是a6
 * ...                              ...
 */
export function shellsortIS<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取1，然后用迭代算出它的最大值
    let increment = 1;
    // 增量数组，相连项没有没有明显的关系所以只能存临时数组里了
    const incrementArr: number[] = [1];
    // 基数数组：a1=3, a2=7, a3=16, a4=41, a5=101
    const radixArr: number[] = [3, 7, 16, 41, 101];
    // index为0时，增量为1已经加到incrementArr了。所以这里index从1开始
    resultIn: for (let index = 1; true; index ++) {
        // 可以看出每项都缺一个，并且是从最后一个开始缺的，所以这里的i从index开始自减
        for (let i = index; i >= 0; i --) {
            // 累乘的基础
            increment = 1;
            // 从a1开始往后累乘
            for (let j = 0; j <= index; j ++) {
                // 缺的就是i，也就是i这项不能参与累乘
                if (i !== j) {
                    increment *= radixArr[j];
                }
            }
            // increment不能超过length
            if (increment < length) {
                incrementArr.push(increment);
            } else {
                break resultIn;
            }
        }
    }
    // 遍历增量数组
    for (let i = incrementArr.length - 1; i >= 0; i --) {
        // 从最大的开始
        increment = incrementArr[i];
        // 插入排序
        insertionSort(array, increment, compareFn);
    }
    return array;
}
/**
 * 希尔算法，Sedgewick改良，1986年发表，比1982年发表的还要好
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：1, 5, 19, 41, 109, 209, 505, 929...
 * 偶数项的通项公式：9*2^i-9*2^(i/2)+1
 * 奇数项的通项公式：8*2^i-6*2^((i+1)/2)+1
 */
export function shellsortSe86<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取1，然后用迭代算出它的最大值
    let increment = 1;
    // 增量数组，相连项没有没有明显的关系所以只能存临时数组里了
    const incrementArr: number[] = [];
    for (let index = 0; true; index ++) {
        if (index % 2 === 0) {
            // 偶数项的通项公式：9*2^i-9*2^(i/2)+1
            increment = 9 * Math.pow(2, index) - 9 * Math.pow(2, index / 2) + 1;
        } else {
            // 奇数项的通项公式：8*2^i-6*2^((i+1)/2)+1
            increment = 8 * Math.pow(2, index) - 6 * Math.pow(2, (index + 1) / 2) + 1;
        }
        // increment不能超过length
        if (increment < length) {
            incrementArr.push(increment);
        } else {
            break;
        }
    }
    // 遍历增量数组
    for (let i = incrementArr.length - 1; i >= 0; i --) {
        // 从最大的开始
        increment = incrementArr[i];
        // 插入排序
        insertionSort(array, increment, compareFn);
    }
    return array;
}
/**
 * 希尔算法，Gonnet改良，1991年发表。
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量increment，是在数组长度上大约取一半再向下取整，之后一直相同处理，直到增量为1
 */
export function shellsortGo<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，初始化时先取length
    let increment = Math.floor((length * 5 - 1) / 11);
    while (increment >= 1) {
        // 插入排序
        insertionSort(array, increment, compareFn);
        // 例如5用公式算出后是2，然后2用公式算出后是0，所以这里强制赋值为1
        if (increment === 2) {
            increment = 1;
        } else {
            // 每轮结束，利用k=k*2+1的关系，求出下一个increment
            increment = Math.floor((increment * 5 - 1) / 11);
        }
    }
    return array;
}
/**
 * 希尔算法，Tokuda(徳田尚之)改良，1992年发表
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：1, 4, 9, 20, 46, 103, 233, 525 ...
 * 通项公式：ceil((9*pow(2.25,i)-4)/5)（其中i为0,1,2,3,4...）
 */
export function shellsortTo<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // increment为增量，先取1，然后用迭代算出它的最大值
    let increment = 1;
    // 增量数组，相连项没有没有明显的关系所以只能存临时数组里了
    const incrementArr: number[] = [];
    for (let index = 0; true; index ++) {
        // 通项公式：ceil((9*pow(2.25,i)-4)/5)，求出increment的最大值
        increment = Math.ceil((9 * Math.pow(2.25, index) - 4) / 5);
        // increment不能超过length
        if (increment < length) {
            incrementArr.push(increment);
        } else {
            break;
        }
    }
    // 遍历增量数组
    for (let i = incrementArr.length - 1; i >= 0; i --) {
        // 从最大的开始
        increment = incrementArr[i];
        // 插入排序
        insertionSort(array, increment, compareFn);
    }
    return array;
}
/**
 * 希尔算法，Ciura改良，2001年发表。
 * @param array 原数组
 * @param compareFn 比较函数
 * 增量不在数组长度基础上折半，而是一个序列：
 * 1, 4, 10, 23, 57, 132, 301, 701, 1750
 * 1, 4, 9, 23, 57, 132, 301, 701, 1577, 3549, 7985, 17965, 40423, 90952, 204643, 460445, 1036002, 2331004
 * 以上两个序列暂无考证究竟是哪一个
 */
export function shellsortCi<T>(array: T[], compareFn = defaultCompare) {
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    let increment: number;
    // 增量序列数组，或者用1, 4, 10, 23, 57, 132, 301, 701, 1750
    const incrementArr: number[] = [1, 4, 9, 23, 57, 132, 301, 701, 1577,
        3549, 7985, 17965, 40423, 90952, 204643, 460445, 1036002, 2331004];
    for (let i = incrementArr.length - 1; i >= 0; i --) {
        increment = incrementArr[i];
        // 选择适当的增量，也可以考虑比length小一点的，以往这里设计的都是比length小即可
        if (increment > Math.floor(length * 4 / 9)) {
            continue;
        }
        // 插入排序
        insertionSort(array, increment, compareFn);
    }
    return array;
}
